/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：TestMain.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-05
Function List ：
Description   ：main function
******************************************************/

#include <stdio.h>  // for printf
#include "DHeap.h"

#define MaxSize (50)

// PrintDHeap for testing
static void PrintDHeap(PriorityQueue H);

/* Fast power function implementation */
#define MOD 1000000007

long long FastPower(long long base, long long power) {
    long long result = 1;

    while (power > 0) {
        if (power & 1) {  // if (power % 2 == 1)
            result = result * base % MOD;
        }

        power >>= 1;  // power = power / 2
        base = (base * base) % MOD;
    }

    return result;
}

void PrintDHeap(PriorityQueue H) {
    int i;
    int j;
    int k;
    int Lev;
    int Pow;
    int CurLevel;
    int CurIndex;
    int RowNum;

    RowNum = 1;    // Number of nodes per row
    CurIndex = 1;  // Current node index
    Lev = Level(H);

    for (CurLevel = 1; CurLevel <= Lev; ++CurLevel) {
        /* Print space at the beginning of the line */
        Pow = (int)FastPower(D, Lev - CurLevel);
        for (i = 0; i < 2 * (Pow - 1); ++i) {
            printf(" ");
        }

        for (i = 0; i < RowNum; ++i) {
            if (CurIndex > Size(H)) {
                break;
            }

            printf("%02d", Retrieve(H, CurIndex++));

            /* Print space in the middle of the line */
            j = 1;
            for (k = 0; k < Lev - CurLevel; ++k) {
                j = j * D + D - 1;
            }

            for (k = 0; k < j * 2; ++k) {
                printf(" ");
            }
        }

        printf("\n");
        RowNum = RowNum * D;  // Update row number
    }

}

// main function
int main(void) {
    PriorityQueue H;
    PriorityQueue H2;
    ElementType A[9];
    int i;
    int j;

    H = Initialize(MaxSize);

    if (H == NULL) {
        printf("PriorityQueue is empty!\n");
    } else {
        printf("PriorityQueue is not empty!\n");
    }

    printf("Insert priority queue: [ ");
    for (i = 1, j = MaxSize / 2; i < MaxSize + 12; i += 3) {
        printf("%02d ", j);
        Insert(j, H);
        j = (j + 21) % MaxSize;
    }
    printf("]\n");

    printf("Print priority queue:\n");
    PrintDHeap(H);
    printf("\n");

    printf("Find min element is %d in priority queue!\n", FindMin(H));
    printf("Delete min element is %d in priority queue!\n", DeleteMin(H));

    printf("Print priority queue:\n");
    PrintDHeap(H);
    printf("\n");

    printf("Increase 2nd key by 60!\n");
    IncreaseKey(2, 60, H);

    printf("Print priority queue:\n");
    PrintDHeap(H);
    printf("\n");

    printf("Decrease 6nd key by 20!\n");
    DecreaseKey(6, 20, H);

    printf("Print priority queue:\n");
    PrintDHeap(H);
    printf("\n");

    printf("Delete 5nd key!\n");
    Delete(5, H);

    printf("Print priority queue:\n");
    PrintDHeap(H);
    printf("\n");

    printf("Destroy priority queue\n");
    Destroy(H);

    printf("Insert priority queue: [ ");
    for (i = 0; i < 9; ++i) {
        A[i] = 9 - i;
        printf("%d ", A[i]);
    }
    printf("]\n");

    H2 = BuildHeap(A, 9);

    printf("Print priority queue:\n");
    PrintDHeap(H2);
    printf("\n");

    printf("Destroy priority queue\n");
    Destroy(H2);

    return 0;
}

// EOF

